\documentclass{ctexart}
\usepackage[hidelinks]{hyperref}%目录
\usepackage{listing}
\usepackage{xeCJK} %导入这个宏包，就可以支持中文
\usepackage{cite}%文献引用
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb,amsfonts}%数学命题，数学字母，排版
\usepackage[a4paper,left=25.4mm,right=25.4mm,top=29.8mm,bottom=29.8mm]{geometry}
\pagestyle{myheadings}
\numberwithin{equation}{section}%以section编号equation
%数学命题环境定义 
%证明环境直接用proof
\theoremstyle{plain} \newtheorem{thm}{定理}[section]
\theoremstyle{plain} \newtheorem*{lemma}{引理}
\theoremstyle{plain} \newtheorem*{prop}{prop}
\theoremstyle{plain} \newtheorem*{property}{性质}
\theoremstyle{definition} \newtheorem*{define}{定义}
\theoremstyle{plain} \newtheorem*{cor}{cor}
\theoremstyle{plain} \newtheorem*{eg}{例}


\title{Data Structure}
\author{陈宇涛,强数2101,3210102287}

\begin{document}
\maketitle

\section*{二叉树和节点设计}
\markright{Data Structure}



\subsection*{数据结构关系}
\begin{flushleft}
    我们要理清的数据结构关系有:BinarySearchTree 和 AvlTree
    结点Node , BinaryNode 和 AvlNode。\\

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.8\textwidth,height=0.8\textwidth]{structure.png}
    \caption{数据结构之间的关系}
    \end{figure} 

   
   
\end{flushleft}



\newpage


\subsection*{设计思路}


\begin{flushleft}
    ~\\
    ~~~~由于这里的各种数据结构的结点是为了数据结构本身服务的，所以我们优先讨论Tree。\\
    一、二叉树\\
    ~~(1)~~对于二叉树来说，需要的是根节点root,并且每一个结点都拥有左节点和右节点来能够做到insert(),remove(),makeEmpty(),printTree()等基本操作。\\

    ~~(2)~~对于二叉搜索树来说，它继承了二叉树的所有性质。由于它是搜索树，所以它的所有结点的数域是一个全序集合。所以树的结构与插入的结点数据排序有关，我们要求每一个结点都要大于左节点，小于右节点来做到一些基本操作:findMin(),findMax().\\


    ~~(3)~~平衡树是在二叉搜索树的基础上添加了balance(),即平衡算法。由于它的平衡条件的判定是根据每一个结点和root的距离，所以要在AvlNode中考虑到。
    同时为了做到平衡，需要一些特殊的函数，rotatewithLeftChild(对左孩子实现单旋转),doublerotatewithLeftChild(对左孩子实现双旋转)等函数。\\
    ~\\

    二、结点\\
    ~~(1)~~定义一个最原始普通的结点Node:即如果某个数据结构能够存放数据和读取数据，我们就称之为Node.\\

    ~~(2)~~对于BinaryNode来说，首先BinaryNode 是一个Node，所以
    它继承了Node的功能，同时由于它是为了BinaryTree服务的，所以它必须能够形成二叉树，即它需要知道左节点和右节点。\\

    ~~(3)~~对于AvlTree来说，首先它是一个BinaryNode，而后它能够实现平衡树的功能。就课堂上的平衡树的平衡条件而言，它需要知道每一个结点的离根节点的距离即为它的高度才可以调节树的平衡状态。\\
\end{flushleft}

\end{document}